1. Field of the Invention
The present invention relates generally to computer networks and, more particularly, to routing packets in an internetwork.
2. Description of the Related Art
Internetworking is the process of establishing and maintaining communications and transferring data among multiple local networks in a distributed network system. The purpose of an internetwork is to provide end-to-end service between one user (a source node) and another user (a destination node).
FIG. 1 depicts an exemplary embodiment of an internetwork system 100, comprising a plurality of routing domains 104-108 coupled to a backbone network 102. In the hierarchically-arranged distributed internetwork system 100, backbone 102 is the top-level, or central, connection path shared by the nodes and networks connected to it, managing the bulk of the traffic between communicating nodes.
Each routing domain 104-108 is a collection of routers that are part of a larger network, such as internetwork 100. Routing domains are also referred to as customer networks or autonomous systems. Domains 104-108 are connected to the backbone 102 through nodes referred to as routers 110, 112 and 114, respectively.
Each routing domain is a collection of one or more local networks, such as local area networks (LAN), metropolitan area networks (MAN), wide area networks (WAN), etc., that are attached to the backbone through one or more routers. In the following discussion, the term "local network" shall be used to refer to all types of networks that may be included in a domain. For example, domain 104 includes local networks 116, 118, and 120. A local network is depicted as a line to which stations can be attached. If a station, or end node, attaches to the bold line, it can transmit packets to, and receive packets from, every other station attached to that same bold line. The source and destination nodes are, typically, computers (workstations and servers) but may be any type of device that can include a network interface card (NIC), such as a printer or modem. Each domain may contain intradomain routers for managing communications among local networks within a particular domain. The routers within a routing domain communicate with each other using a common intradomain routing protocol, such as Routing Information Protocol (RIP) and Integrated IS-IS (Intermediate System-to-Intermediate System) protocols.
In order to reduce design complexity, most networks are organized as a series of hardware and software levels or "layers" within each node. These layers interact to format data for transfer between, for example, a source node and a destination node communicating over the network. Specifically, predetermined services are performed on the data as it passes through each layer and the layers communicate with each other by means of predefined protocols. This layered design permits each layer to offer selected services to other layers using a standardized interface that shields those layers from the actual implementation details of the services.
In an attempt to standardize network architectures, that is, the sets of layers and protocols used within a network, a generalized model has been proposed by the International Standards Organization (ISO). The model, called the Open Systems Interconnection (OSI) reference model, is directed to the interconnection of systems that are "open" for communication with other systems. The proposed OSI model has seven layers which are termed, in ascending interfacing order, the physical, data link, network, transport, session, presentation, and application layers. These layers are arranged to form a "protocol stack" in each node of the network.
FIG. 2 illustrates a schematic block diagram of OSI protocol stacks 202-208 used to transmit data between, for example, a source node 123 and a destination node 126 through routers 130 and 132, all of which are elements of internetwork 100. Each protocol stack is structured according to the OSI seven-layer model; accordingly, each stack comprises a collection of protocols, one per layer. The routers will make use of the lower three OSI layers, known as the subnet layers, to move the data along to the next router or the destination node. As can be seen, the protocol stacks 202-208 are physically connected through communications channels 118 at physical layers 230-250; 117 at physical layers 250-260; and 120 at physical layers 260-270. Data flow is schematically illustrated by solid arrows. For ease of description, the protocol stack 202 will be described.
Broadly stated, the physical layer 230 transmits a raw data bit stream over a communication channel 118, while the data link layer 232 manipulates the bit stream and transforms it into a datastream that appears free of transmission errors. This latter task is accomplished by dividing the transmitted data into frames and transmitting the frames sequentially, accompanied with error correcting mechanisms for detecting or correcting errors. The network layer 234 routes data packets from the source node 123 to the destination node 126 by selecting one of many alternative paths through the physical network. The transport layer 236 accepts the datastream from the session layer 238, apportions it into smaller units (if necessary), passes the smaller units to the network layer 234 and provides appropriate mechanisms to ensure that all the units arrive correctly at the destination node.
The session layer 238 establishes data transfer "sessions" between software processes on the source and destination nodes, along with management of such sessions in an orderly fashion. That is, a session not only allows ordinary data transport between the nodes, but it also provides enhanced services in some applications. The presentation layer 240 performs frequently-requested functions relating to the presentation of transmitted data, including encoding of data into standard formats, while the application layer 242 contains a variety of protocols that are commonly needed by processes executing on the nodes.
Data transmission over the internetwork 100 therefore consists of generating data in, for example, a sending process 210 executing on the source node 123, passing that data to the application layer 242 and down through the layers of the protocol stack 202, where the data are sequentially formatted as a packet for delivery onto the channel 118 as bits. Those packet bits are then transmitted to the protocol stacks 204 and 206 of the routers 130 and 132, respectively, and finally to stack 208 of the destination node 126, where they are passed up that stack to a receiving process 212.
Although actual data transmission occurs vertically through the stacks, each layer is programmed as though such transmission were horizontal. That is, each layer in the source node 123 is programmed to transmit data to its peer layer in the destination node 126, as schematically shown by dashed arrows in FIG. 2. To achieve this effect, each layer of the protocol stack 202 in the source node 123 typically adds information (in the form of a header field) to the data packet generated by the sending process as the packet descends the stack. At the destination node 126, the various headers are stripped off one-by-one as the packet propagates up the layers of protocol stack 208 until it arrives at the receiving process 212.
The source and destination network layer addresses are typically hierarchical and consist of a plurality of elements, including a network number and a node address. Within each local network, each node has a unique node address that identifies a particular node in a particular local network. The node address is also known as a node ID or node number.
In addition to a unique node address, each node in a local network has a common network number. Within each domain, routing is based on this network number and, therefore, these numbers are assigned so that they are unique within each particular local network. That is, the network numbers are arbitrary values that are assigned identically to each node in a local network. Routers 110-114 (FIG. 1) "advertise" to the backbone the network numbers in their domain networks that they can access. A network number is also referred to as a local network number or Internetwork Packet Exchange.TM. (IPX.TM.) network number. The network layer address, which includes both the network number and the node address, is also referred to as the local network address or IPX network address.
Presently, in order to support end-to-end connectionless communications between all nodes in an internetwork, every local network must have a unique network number to distinguish the nodes in that network from other nodes in other local networks in the internetwork. Thus, no two local networks in an entire internetwork may have the same network number.
However, there has been no global enforcement regarding the assignment of network numbers to local networks, resulting in arbitrarily-assigned network number values within an internetwork. Accordingly, as the number of local networks in the internetwork increases, so does the incidence of conflicting network layer addresses due to the assignment of non-unique network numbers. This phenomenon results in address collisions, adversely affecting the ability of the internetwork to reliably route packets to a particular destination node.
In addition, in recent times, the size of internetworks has increased dramatically, placing a burden on routers to support large numbers of local networks. For example, some routers perform route aggregation as a technique for summarizing a large quantity of network numbers by associating them with a particular domain, enabling an implementing router to identify a range of network numbers with a relatively small amount of information. Oftentimes however, conventional routing protocols such as IPX RIP do not support route aggregation. Thus, in order to provide the ability to communicate with every node, the backbone must allocate resources for storing and retrieving every network number for every local network in the internetwork.
Although some routing protocols such as IS-IS and NetWare.RTM. Link Services Protocol.TM. (NLSP.TM.) software implement some form of aggregation, such protocols still suffer from the above drawback of being unable to properly identify local networks when non-unique network numbers exist. Furthermore, although aggregation may be possible, oftentimes the manner in which the network numbers are assigned does not necessarily lend itself to summarization.
One conventional approach to ensuring that all local networks have a unique network number has been to require all nodes in a local network to change the network number associated with that local network prior to connecting to the internetwork. One drawback to this approach is that the routers must be reconfigured to support these new network numbers. In addition, once all the local networks in the internetwork have a globally-unique network number, the backbone must still provide the resources necessary to maintain the large number of network numbers in the internetwork. Furthermore, routers that cannot aggregate are incapable of servicing the resulting large number of network numbers.
In order to maintain unique network layer addresses in an internetwork having local networks with redundant network numbers, some routing protocols, such as AURP (AppleTalk.RTM. Update Routing Protocol) of the AppleTalk Protocol Suite, provide a unique network number for every local network in the internetwork. This information, typically maintained as part of the routing table, simply provides a one-to-one mapping of a non-unique network number to a unique network number. Although these types of protocols result in a unique network number for each local network, they do not address the inability of certain routers to support the large number of network numbers that must be addressed by the router. In other words, a router unable to support the large number of potentially non-unique network numbers will also be unable to support the same number of globally-unique network numbers. Furthermore, conflicts often arise between the new network number and certain upper-layer protocols that are sensitive to address changes.
Another conventional approach is to expand the address space of nodes coupled to the internetwork to provide new and modified elements to a conventional hierarchical network layer address. This approach is described in pending U.S. patent application Ser. No. 08/499,103, entitled "Network Addressing Arrangement For Backward Compatible Routing of an Expandable Address Space," naming as inventors Radia J. Perlman and Neal D. Castagnoli, filed on Jul. 6, 1995, and assigned to the assignee of the present invention. However, this approach requires time consuming and costly upgrading of all nodes in a domain to support this expanded address space.
What is needed, therefore, is a means for providing addressing information to reliably route communications among local networks of an internetwork in a manner that is not adversely affected by redundant network numbers and that does not require large amounts of addressing information to be maintained by the backbone or routers.